Skip to main content

Greedy Algorithms

Greedy algorithms are a class of algorithms used to solve optimization problems by making the locally optimal choice at each step with the hope of finding the global optimum.

Characteristics Suitable for Greedy Algorithms​

Greedy algorithms are particularly suitable for problems that exhibit:

  • Greedy Choice Property: The local optimal choices can lead to a globally optimal solution.
  • Optimal Substructure: The solution to the problem includes solutions to its subproblems.

Problem-Solving with Greedy Algorithms​

  1. Problem Analysis: Define the state, objectives, and constraints.
  2. Determine Greedy Strategy: Identify how to make a greedy choice at each decision point.
  3. Proof of Correctness: Validate the greedy choice property and optimal substructure, often through mathematical proofs such as induction.

Comparison with Dynamic Programming​

Greedy algorithms differ significantly from dynamic programming:

  • Dynamic Programming: Takes into account all previous decisions and uses solutions to past subproblems to solve current subproblems.
  • Greedy Algorithms: Do not look back at previous decisions; they focus only on making the most favorable choice at each step.

Examples​

  1. Fractional Knapsack Problem: Select items based on the highest value/weight ratio to maximize total value without exceeding the weight capacity.
  2. Huffman Coding: Build an optimal binary tree for data compression by repeatedly merging the two nodes with the smallest frequencies.
  3. Dijkstra's Algorithm: Find the shortest path from a single source node to all other nodes in a graph by exploring the nearest unexplored node first.
  4. Activity Selection Problem: Given a set of activities with start and finish times, select the maximum number of activities that can be performed by a single person assuming that a person can only work on a single activity at a time.
  5. Prim's and Kruskal's Algorithms: Used to find the minimum spanning tree of a graph (a tree that connects all vertices with the minimum total edge weight).

Advantages and Limitations​

  • Efficiency: Greedy algorithms typically run faster due to simpler logic and fewer calculations. For example, the greedy solution for the coin change problem runs in O(amt/min⁡(coins))O (\text{amt} / \min (\text{coins})).
  • Accuracy: Greedy algorithms can sometimes fail to find the optimal solution, particularly when the problem structure is complex or unusual.